package my.jwds.p386;

import java.util.ArrayList;
import java.util.List;

public class LexicalOrder {

    public static void main(String[] args) {

        Solution obj = new Solution();
        long start = System.currentTimeMillis();
        System.out.println(obj.lexicalOrder(103));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>();
            dfs(0,1,n,res);
            return res;
        }


        void dfs(int base,int start,int end,List<Integer> res){

            for (int i = start; i < 10; i++) {
                int num = base+i;
                if (num > end)break;
                res.add(num);
                if (num * 10 <= end){
                    dfs(num*10,0,end,res);
                }
            }

        }
    }


    static class Solution1 {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>();
            int num = 1;

            for (int i = 0; i < n; i++) {
                res.add(num);

                if (num * 10 <= n){
                    num *= 10;
                }else{

                    while(num % 10 == 9 || num+1 >n)num/=10;
                    num++;

                }

            }


            return res;
        }

    }
}